package com.LeeCode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 合并多棵二叉搜索树
 */

public class Code1932 {
    public static void main(String[] args) {

    }

    public TreeNode canMerge(List<TreeNode> trees) {
        if (trees == null || trees.isEmpty()) return null;
        // 建立映射关系
        Map<Integer, TreeNode> rootValToTree = new HashMap<>();
        Map<Integer, TreeNode> leafToRoot = new HashMap<>();
        for (TreeNode tree : trees) {
            rootValToTree.put(tree.val, tree);
            if (tree.left != null) leafToRoot.put(tree.left.val, tree);
            if (tree.right != null) leafToRoot.put(tree.right.val, tree);
        }
        // Step 1：寻找唯一根节点
        TreeNode root = findCandidateRoot(trees, leafToRoot);
        if (root == null) return null;

        // Step 2: 构建完整树
        buildTree(root, rootValToTree);

        // Step 3、4: 判断小二叉树是否用完 && 验证是否是 BST
        if (rootValToTree.size() == 1 && isValidBST(root)) {
            return root;
        }

        return null;
    }


    // 找到候选根节点（即根值不在其他树的叶子中的那个）
    private TreeNode findCandidateRoot(List<TreeNode> trees, Map<Integer, TreeNode> leafToRoot) {
        Set<Integer> integers = leafToRoot.keySet();
        TreeNode root = null;
        for (TreeNode tree : trees) {
            if (!integers.contains(tree.val)) {
                if (root == null) {
                    root = tree;
                } else {
                    return null;  // 根节点不唯一
                }
            }
        }
        return root;
    }

    // 递归构建二叉树
    private void buildTree(TreeNode root, Map<Integer, TreeNode> rootValToTree) {
        if (root == null) return;
        if (root.left != null) {
            TreeNode leftReplace = rootValToTree.get(root.left.val);
            if (leftReplace != null) {
                root.left = leftReplace;
                rootValToTree.remove(leftReplace.val);
                buildTree(root.left, rootValToTree);
            } else {
                buildTree(root.left, rootValToTree);
            }
        }
        if (root.right != null) {
            TreeNode rightReplace = rootValToTree.get(root.right.val);
            if (rightReplace != null) {
                root.right = rightReplace;
                rootValToTree.remove(rightReplace.val);
                buildTree(root.right, rootValToTree);
            } else {
                buildTree(root.right, rootValToTree);
            }
        }
    }

    // 同98题
    private TreeNode prev = null;

    private boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (!isValidBST(root.left)) return false;
        if (prev != null && prev.val >= root.val) return false;
        prev = root;
        return isValidBST(root.right);
    }

}
